//环形子数组的最大和
class Solution {
    public:
        int maxSubarraySumCircular(vector<int>& nums) {
            //dp
            int n = nums.size();
            vector<int> bigdp(n),smalldp(n);
            bigdp[0] = smalldp[0] = nums[0];
            int sum = nums[0];
            for(int i = 1; i < n; i++)
            {
                sum += nums[i];
                bigdp[i] = max(bigdp[i-1]+nums[i],nums[i]);
                smalldp[i] = min(smalldp[i-1]+nums[i],nums[i]);
            }
            int big,small;
            big = *std::max_element(bigdp.begin(),bigdp.end());
            small = *std::min_element(smalldp.begin(),smalldp.end());
            if(small == sum) small = 0;
            return big > (sum - small) ? big : sum - small;
        }
    };